package _11_整理题目._6_模拟设计._区间覆盖问题;

import org.junit.Test;

import java.util.Arrays;

/**
 * https://leetcode-cn.com/problems/merge-intervals/
 *
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
 * 请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
 *
 * 思路：
 *      两个区间排序后一共三种关系：https://leetcode-cn.com/problems/merge-intervals/solution/chi-jing-ran-yi-yan-miao-dong-by-sweetiee/
 *      先排序，在遍历 两两合并
 *          如果当前区间起始值 > 结果数组最后一个区间的终止值时，直接加入结果
 *          否则，合并到上一个区间，即 更新上一个区间的结尾值
 */
public class _02_合并区间 {

    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
        int n = intervals.length;
        int[][] res = new int[n][2];
        int index = 0;
        for (int[] interval : intervals) {
            if (index == 0 || interval[0] > res[index - 1][1]) {
                res[index++] = interval;
            } else if(interval[0] <= res[index-1][1]) {
                res[index - 1][1] = Math.max(interval[1], res[index - 1][1]);
            }
        }
        return Arrays.copyOf(res, index);
    }

    @Test
    public void main() {
        int[][] intervals = {{1, 3}, {8, 10}, {2, 6}, {15, 18}};
        int[][] result = merge(intervals);
        for (int[] ints : result) {
            System.out.println(Arrays.toString(ints));
        }

        int[][] results = merge(intervals);
        for (int[] ints : results) {
            System.out.println(Arrays.toString(ints));
        }
    }

    public int[][] merge2(int[][] intervals) {
        return new int[0][0];
    }

}